package arrAndstr;

/*
    55. 跳跃游戏
 */
public class T55 {

    public static void main(String[] args) {
        int[] array = new int[]{5,9,3,2,1,0,2,3,3,1,0,0};

        System.out.println(canJump(array));
    }

    public static boolean canJump(int[] nums) {
        int len = nums.length;

        int index = 0;
        while(index < len-1) {    // 最后一个下标
            if(nums[index] == 0) return false;
            int leftIndex = index+1;
            int rightIndex = index + nums[index];
            index = getNextIndex(nums, leftIndex, rightIndex);
        }

        return true;
    }

    public static int getNextIndex(int[] array, int leftIndex, int rightIndex) {
        int maxIndex = leftIndex;
        int maxLen = leftIndex + array[leftIndex];
        int len = array.length;
        for(int i=leftIndex + 1; i<=rightIndex && i<len; i++) {
            if(array[i]+i > maxLen) {
                maxIndex = i;
                maxLen = array[i] + i;
            }
        }
        return maxIndex;
    }
}
